package Z.dailyExercise.May;

import java.util.WeakHashMap;

public class _75颜色分类 {
    public static void main(String[] args) {
        _75颜色分类 test = new _75颜色分类();
        test.sortColors(new int[]{2,0,2,1,1,0});

    }

    /**
     * 快排 超时。。。
     * @param nums
     */
    public void sortColors(int[] nums) {
        helper(nums,0,nums.length-1);
        System.out.println(nums);


    }
    public void helper(int[] nums,int left,int right){

        while (left < right){
            int base = nums[left];
            int low = left;
            int high = right;

            while (low < high){
                while (low < high && nums[high]>=base){
                    high--;
                }
                nums[low] = nums[high];

                while (low < high && nums[low] < base){
                    low++;
                }
                nums[high] = nums[low];
            }
            nums[low] = base;

            helper(nums,left,low);
            helper(nums,low+1,right);
        }
    }

    /**
     * 题解：因为本题只有 012三个数字 所以可以采用双指针
     * 一个指向0 一个指向1 0 1排好之后2就自然是好的了
     * 如果遍历到0 交换之后如果p0小于p1了，说明两个指针之间都是1 所以被交换过去的肯定是个1 那么就将i所在与p1交换 然后均向后移动
     * 遍历到1 只是p1移动
     */
    public void sortColors1(int[] nums) {
        int p0=0,p1=0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1){
                int temp = nums[p1];
                nums[p1] = nums[i];
                nums[i] = temp;
                p1++;
            }else if (nums[i] == 0){
                int temp = nums[p0];
                nums[p0] = nums[i];
                nums[i] = temp;
                if (p0 < p1){
                    temp = nums[p1];
                    nums[p1] = nums[i];
                    nums[i] = temp;
                }
                p0++;
                p1++;

            }

        }


    }
}
